package zw_1_100.zw_83_删除排序链表中的重复元素;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    /**
     * 指定 cur 指针指向头部 head
     * 当 cur 和 cur.next 的存在为循环结束条件，当二者有一个不存在时说明链表没有去重复的必要了
     * 当 cur.val 和 cur.next.val 相等时说明需要去重，则将 cur 的下一个指针指向下一个的下一个，这样就能达到去重复的效果
     * 如果不相等则 cur 移动到下一个位置继续循环
     * 时间复杂度：O(n)
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 递归
     * @param head
     * @return
     */
//    public ListNode deleteDuplicates(ListNode head) {
//        //1：这种情况不可能有相同节点，直接返回
//        if (head == null || head.next == null) {
//            return head;
//        }
//        //2：当前节点与下个节点一样
//        if (head.val == head.next.val) {
//            //3：将当前节点的下个节点跳过，指向递下下个归后的结果
//            head.next = deleteDuplicates(head.next.next);
//            //4：为了防止删除了下个节点，与下下个节点还是一样，继续递归，如[1,1,1]这种情况，跳过了第二个节点，还剩下[1,1]
//            return deleteDuplicates(head);
//        }
//        //5：当前节点与下个节点不一样，继续递归下个节点，递归函数继续判断是否与下下个节点一样(见2))
//        deleteDuplicates(head.next);
//        return head;
//    }


    public class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

